МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Алгоритми для виконання операцій з довгими числами
Лабораторна робота № 2
Виконав:
студент гр.ІБ-44
Перевірив:
Костів Ю.М.
Львів – 2010
Мета роботи: - вивчити алгоритми множення та ділення довгих чисел та навчитись розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері ; дослідити швидкодію виконання операцій над довгими числами .
Завдання: - поділити два довгих числа.
Список ідентифікаторів констант, змінних і функцій, використаних у головній програмі і підпрограмах та їх пояснення
MaxDig – константа що вказує на максимальну довжину масиву;
Osn – константа що вказує на основу;
ch – елемент типу CHAR;
b,c,a,sp,j,i - змінні, що використовуються у підпрограмах
Процедури :
Readlong- введення довгого числа
Writelong – виведення довгого числа
Sub - віднімання
Mul – множення
More - порівняння
FindBin – функція ділення стовпчиком
MakeDel – вираховування зсуву
Long_Div_Long – ділення
const maxdig=1000;
osn=10000;
Type Tlong=Array[0..maxdig] of integer;
procedure readlong(var a:Tlong); {vvid}
var ch:char; i:integer;
begin
fillchar(a,sizeof(a),0);
read(ch);
while not (ch In['0'..'9']) do read(ch);
while ch In['0'..'9'] do begin
for i:=a[0] downto 1 do begin
a[i+1]:=a[i+1]+(longint(a[i])*10) div osn;
a[i]:=(longint(a[i])*10) mod osn;
end;
a[1]:=a[1]+ord(ch)-ord('0');
if a[a[0]+1]>0 then inc(a[0]);
read(ch);
end;
end;
procedure writelong(const a:Tlong); {vuvid}
var ls,s:String;
i:integer;
begin
str(osn div 10,ls);
write(a[a[0]]);
for i:=a[0]-1 downto 1 do begin
str(a[i],s);
while length(s)<length(ls) do s:='0'+s;
write(s);
end;
end;
Procedure Sub (Var A : TLong; Const B : TLong; Const sp : Integer); {vidnimannya}
Var i, j : Integer;
Begin
For i := 1 To B[0] Do
Begin Dec(A[i+sp], B[i]);
j:= i;
while (A[j+sp] < 0) and (j <= A[0]) Do
Begin
Inc(A[j+sp], Osn) ;
Dec(A[j+sp+1]); Inc(j);
end;
End;
i := A[0];
While (i > 1) And (A[i] = 0) Do Dec(i);
A[0] := i
End;
Procedure Mul(Const A : TLong; Const K : Longint; Var C : TLong);{mnogennya}
Var i : Integer;
Begin
FillChar (c, SizeOf(c), 0);
If K = 0 Then Inc(c[0])
Else Begin
For i:= 1 To A[0] Do
Begin
C[i+1] := (LongInt(A[i]) * K + C[i]) Div Osn;
C[i] := (LongInt(A[i])* K + C[i]) Mod Osn
End;
If C[A[0]+1] > 0 Then C[0]:= A[0] + 1
Else C[0]:= A[0]
End;
End;
Function More(Const A, B : Tlong; Const sdvig : Integer) : Byte; {porvn9nn9}
Var i : Integer;
Begin
If A[0] > B[0] + sdvig Then More := 0
Else
If A[0] < B[0] + sdvig Then More := 1
Else Begin
i := A[0];
While (i > sdvig) And
(A[i] = B[i-sdvig]) Do Dec(i);
If i = sdvig Then Begin
More:=0;
For i := 1 To sdvig Do
If A[i] > 0 Then Exit;
More := 2;
end
Else More := Byte(A[i] < B[i-sdvig])
End
end;
Function FindBin(Var Ost : Tlong; Const B : TLong; Const sp : Integer) : Longint; {func dilennya stovp4ikom}
Var Down, Up : Word; C : TLong;
Begin
Down := 0;Up := osn;
While Up - 1 > Down Do
Begin
Mul(B, (Up + Down) Div 2, C);
Case More(Ost, C, sp) Of
0: Down := (Down + Up) Div 2;
1: Up := (Up + Down) Div 2;
2: Begin Up := (Up + Down) Div 2; Down := Up End;
End;
End;
Mul(B, (Up + Down) Div 2, C);
If More (Ost, C, 0) = 0 Then Sub(Ost, C, sp)
Else begin Sub (C, Ost, sp); Ost := C end;
FindBin := (Up + Down) Div 2;
End;
Procedure MakeDel(Const A, B : TLong; Var Res, Ost : TLong); {vuraxuvann9 zsuvu}
Var sp : Integer;
Begin
Ost := A;
sp := A[0] - B[0];
If More(A, B, sp) = 1 Then Dec(sp);
Res[0] := sp + 1;
While sp >= 0 Do
Begin
Res[sp + 1] := FindBin(Ost, B, sp);
Dec(sp);
End;
End;
Procedure Long_Div_Long(Const A, B : TLong; Var Res, Ost : TLong); {dilennya}
Begin
FillChar(Res, SizeOf(Res), 0); Res[0] := 1;
FillChar(Ost, SizeOf(Ost), 0); Ost[0] := 1;
Case More(A, B, 0) Of
0: MakeDel(A, B, Res, Ost);
1: Ost:=A...
